It is desirable to implement routing systems that search network route caches to find the forwarding information for packets to be routed rather than searching a complete forwarding information base, FIB, that contains the forwarding information for all active routes for that purpose; this invention provides a mechanism for efficiently distributing the routing load between a network route cache and a host route cache (or optionally a FIB.) It is desirable to distribute the routing load between a network route cache and a host route cache efficiently because it reduces the number of entries that must be supported in those caches.
A router is any device that is capable of routing information between networks using a FIB, that it uses to find the forwarding information for packets destined for all known networks. A known network or host may be defined as a network or host for which there is a route in the FIB that has valid forwarding information.
A router may employ a variety of mechanisms to route the packets. The router may route packets by searching the FIB for a route to the destination of the packets and then forwarding the packet with the forwarding information from the matching route in the FIB. In addition to searching the FIB, a router may employ caching mechanisms in hardware or in software that hold forwarding information for frequently accessed destinations. These caching mechanisms may employ any combination of a host route cache and a network route cache, at any one time the caches are capable of routing to only a subset of the destinations that are accessible using the information from the FIB. Both of these caches are searched with the destination internet protocol, IP, address of the packet to be routed. The entries in the host route cache will match at most one address, while the entries in a network route cache may match one or more addresses. The entries in the network route cache and in the host route cache will contain forwarding information that is to be used for packets that are routed using a matching cache entry. The advantage of using these caches is that it is less expensive to build a high performance routing cache than it is to build a high performance FIB, as a result cost savings can be realized by using a set of high performance caches (network and host route caches) and a lower performance FIB in place of a single high performance (and expensive) FIB.
The network route cache is used to provide subnet based route lookup functionality. The network route cache is searched using the destination address of a packet to be routed and if the cache contains a route to the destination address of the packet it will route the packet using the forwarding information from the matching route. Thus, the network route cache may be used as a cache to store a subset of all of the routes that are known to the router.
It is desirable to use a combination of a network route cache and host route cache efficiently such that the size of these two caches may be limited for a reduction in the cost of devices that employ these two caches. Therefore, there is need in the current technology for new methods and techniques that will effectively and efficiently use the limited amount of space in a network route cache.
Using present methods many routers store all of the active entries from their RIB, routing information base, in a high performance FIB that is used to make the majority of the routing decisions, and this is very expensive. These routers do not route packets using a network route cache, these routers route using the full set of active routes in the RIB along with optionally a host route cache. This requires a very large and expensive forwarding table in the high performance routing path. Embodiments of the invention allow routers to efficiently manage a network route cache; alternate mechanisms for maintaining such a cache (for example LRU [Least Recently Used] or random replacement) do not lead to efficient cache utilization.
Therefore, the current technology is limited in its capabilities and suffers from at least the above constraints.